#-*- coding: utf-8 -*-
# lista = [1, 2, 3, 4, 12, 22, 15, 44, 3, 4, 4, 4, 7, 7, 44, 77, 100]
# new_dict = {}
# for item in lista:
#     if item not in new_dict.keys():
#         new_dict[item] = lista.count(item)
# print(new_dict)
#
# def prime1(n):
#     result=[]
#     for i in range(2,n):
#         for j in range(2,i):
#             if i%j==0:
#                 break
#         else:
#             result.append(i)
#     return result
#
#
# print(prime1(5))


def sift(li, low, high):
    """
    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个元素的位置
    :return:
    """
    i = low # i最开始指向根节点
    j = 2 * i + 1 # j开始是左孩子
    tmp = li[low] # 把堆顶存起来
    while j <= high: # 只要j位置有数
        print(li)
        if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子有并且比较大
            j = j + 1  # j指向右孩子
        if li[j] > tmp:
            li[i] = li[j]
            i = j           # 往下看一层
            j = 2 * i + 1
        else:       # tmp更大，把tmp放到i的位置上
            li[i] = tmp     # 把tmp放到某一级领导位置上
            break
    else:
        li[i] = tmp  # 把tmp放到叶子节点上

# sift([9,99,5,4,7],0,4)
li = [1,9,99,7,4,5]
for  i  in range(len(li)-1-1//2,-1,-1):
    sift(li,i,len(li)-1)
print(li)